package SwordOffer2;

public class day9_3 {
    /*
     * 1.循环链表，找到链表中的最大值maxLen和下标max，
     * 2.判断待插入元素insertVal是否大于左边小于右边，若成立插入该元素，退出循环，
     * 3.若循环一轮未找到insertVal插入位置，说明该元素不在链表[min,max]的范围，insertVal<min||insertVal>max,
     *   退出循环，将元素插入到max下标之后，next指向min，保持成环
     * 4.返回记录head节点的res
     * */
    public Node insert(Node head, int insertVal) {
        Node res = head;
        Node max = head;
        int count = 0;
        boolean bool = false;
        int maxLen = Integer.MIN_VALUE;
        if (head == null) {
            Node node = new Node(insertVal);
            head = node;
            head.next = head;
            return head;
        }
        while (head.next != null) {
            count++;
            if (maxLen < head.val) {
                maxLen = head.val;
                max = head;
            }
            if (head.val <= insertVal && head.next.val >= insertVal) {
                Node node = new Node(insertVal);
                Node temp = head.next;
                head.next = node;
                node.next = temp;
                break;
            }
            if (count != 0 && head.next.val == res.val) {
                bool = true;
                break;
            }
            head = head.next;
        }
        if (bool) {
            Node node = new Node(insertVal);
            Node temp = max.next;
            max.next = node;
            node.next = temp;
        }
        return res;
    }
}
